package _18_剑指OfferII;

import java.util.ArrayList;
import java.util.List;

public class _080_剑指OfferII含有k个元素的组合 {


    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {

        dfs(n, 1, k, new ArrayList<Integer>());

        return result;
    }

    private void dfs(int n, int index, int k, List<Integer> list) {
        if (n - index + 1 < k) return;
        if (k == 0) {
            result.add(new ArrayList<>(list));
            return;
        }

        for (int i = index; i <= n; ++i) {
            list.add(i);
            dfs(n, i + 1, k - 1, list);
            list.remove(list.size() - 1);
        }
    }

}
